home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / gnugo1_1.lha / gnugo / Documentation < prev    next >
Text File  |  1989-03-07  |  11KB  |  292 lines

  1.                GNU GO - the game of Go (Wei-Chi)
  2.                Version 1.1   last revised 3-1-89
  3.          Copyright (C) Free Software Foundation, Inc.
  4.                     written by Man L. Li
  5.                     modified by Wayne Iba
  6.                    documented by Bob Webber
  7.  
  8. This program is free software; you can redistribute it and/or modify
  9. it under the terms of the GNU General Public License as published by
  10. the Free Software Foundation - version 1.
  11.  
  12. This program is distributed in the hope that it will be useful,
  13. but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15. GNU General Public License in file COPYING for more details.
  16.  
  17. You should have received a copy of the GNU General Public License
  18. along with this program; if not, write to the Free Software
  19. Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  20.  
  21. Please report any bug/fix, modification, suggestion to
  22.  
  23. mail address:   Man L. Li
  24.                 Dept. of Computer Science
  25.                 University of Houston
  26.                 4800 Calhoun Road
  27.                 Houston, TX 77004
  28.  
  29. e-mail address: manli@cs.uh.edu         (Internet)
  30.                 coscgbn@uhvax1.bitnet   (BITNET)
  31.                 70070,404               (CompuServe)
  32.  
  33.  
  34. value 0 always used to mark empty square
  35. value 1 always used to indicate white
  36. value 2 always used to indicate black
  37.  
  38. main()
  39.     Shows instructions.
  40.  
  41.     If old game then read in information otherwise
  42.     Initializes the board stored in the board array p to zero.
  43.  
  44.     Requests handicap (stored in local variable i.)
  45.  
  46.     Displays board.
  47.  
  48.     Asks which side you want to play (stored in local variable ans)
  49.     mymove and umove indicate color played by computer and user, respectively.
  50.     
  51.     if user black in handicap game or white in even game, computer goes first.
  52.  
  53.     making a move means updating the board with the numeric value for color
  54.     of player.  genmove takes board indices i & j as reference parameters
  55.     and returns the ones that correspond to a new move for the computer,
  56.     it does not update the board.  the routine examboard then clears
  57.     of dead pieces (of the color passed as its parameter).  after the board 
  58.     has been updated, showboard displays board.
  59.  
  60.     routine getmove convert the string the user types in into a valid
  61.     move i,j pair.
  62.  
  63.     getmove manipulates global variable stop to indicate when game is
  64.     done.
  65.  
  66.     the game stop after both pass, the user want to quit and save game
  67.     or the user stop the game
  68.  
  69.     at the end of game, if the user types y to ``count score'' prompt,
  70.     then endgame is invoked, otherwise the program exits.
  71.  
  72.  
  73. showboard()
  74.     displays go board with algebraic notation on borders.  special logic
  75.     to make sure handicap markers are displayed appropriately done by
  76.     brute force.
  77.  
  78.  
  79. getmove(move, i, j)
  80.     if move = "stop" then global variable play changed to 0 exiting loop
  81.  
  82.     if move = "save" then write game information to file and exit by
  83.     setting global variable to -1
  84.  
  85.     if move = "pass" then increment global variable pass
  86.     otherwise, clear pass flag getij is invoked to convert move into i and j
  87.     coordinates.
  88.     if the board position is not empty, the last piece captured by
  89.     computer, or suicide predicate is true, then the move is flagged as 
  90.     illegal and getmove recurses.
  91.  
  92.  
  93. getij(move, i, j)
  94.     move string converted to board coordinates.
  95.  
  96.  
  97. genmove(i, j)
  98.     generates computers move and returns it in pointers i & j.
  99.     invoke eval(umove) to re-evaluate liberty of opponent pieces
  100.  
  101.     findwinner looks for pieces of user that only have 3 or less liberties.
  102.     findsaver looks for pieces of computer that only have 3 or less liberties.
  103.     findpat looks for a pattern in stored database that can be used here.
  104.  
  105.     STRATEGY:
  106.        choose move with maximum value from the followings:
  107.  
  108.        find opponent piece to capture or attack with less than four liberties
  109.        save any piece if threaten with less than four liberties
  110.        try to match local play pattern for new move
  111.  
  112.        no urgent move then do random move
  113.           when generating random move, bias row and column x
  114.           by rejecting the first x that satisfies
  115.           ((x < 2) || (x > 16) || ((x > 5) && (x < 13)))
  116.           and on second try, reject an x that satisfies
  117.           ((x < 2) || (x > 16))
  118.           on third try, take what you get.  done independently for
  119.           i and j.
  120.           invoke countlib to count liberties, if spot already taken
  121.             or liberties (taken off global lib) 0 or 1 or fill in own eye then
  122.             reject.
  123.  
  124.           if number of try equals to MAXTRY then pass
  125.  
  126.     after following STRATEGY to determine move, print it.
  127.  
  128.  
  129. seed(i) 
  130.    sets up a seed.  two versions depending on whether Sun (which uses
  131.    gettimeofday to set seed) or IBM PC (which uses interrupt 21 to get system
  132.    time).
  133.  
  134.  
  135. random(i)
  136.   simple conguence random number generator.  only used for making ``random''
  137.   moves, either in genmove() or in opening().
  138.  
  139.  
  140. eval(color)
  141.   evaluate liberties of pieces of a particular color using countlib.
  142.   result stored in global array l.
  143.  
  144.  
  145. examboard(color)
  146.   invokes eval(color)
  147.   remove pieces with zero liberties, updating count of pieces captured
  148.   in variables mk and uk for computer and user respectively.
  149.  
  150.  
  151. suicide(i, j)
  152.   check to see if new move is suicide via countlib().  if it is, check to 
  153.   see if it kills computer's pieces via eval() or if Ko takes place
  154.   returns 0 if move is good.
  155.  
  156.  
  157. countlib(m, n, color)
  158.     initializes global array ml to 1's and then uses routine count() to
  159.     count liberties at each square.
  160.  
  161.  
  162. count(i, j, color)
  163.     count liberties at given square. zero out value of that square.
  164.     if neighbor is still unmarked and its value on the board is still zero,
  165.      then it is marked as zero and lib count is updated, 
  166.     if neighbor is same color and unmarked, then count is recursively called.
  167.     this is done for all four neighbors, then the routine returns.
  168.  
  169.     essentially this does a connected component search on region connected
  170.      to location i & j.
  171.  
  172.  
  173. findnextmove(m, n, i, j, val, minlib)
  174.    used by findsaver() to find next move for defense.
  175.    find new move i, j from group containing m, n
  176.    uses global array ma to keep track of where it has been.
  177.    for each neighbor, checks to see if it is empty.  If so, then it
  178.        calculate the new liberty and the relative value of the move.
  179.        Otherwise recurses on that neighbor.  After new move is found compare
  180.        it with other move and use the one with higher value.
  181.    returns 0 if couldn't find move.
  182.  
  183.  
  184. findwinner(i, j, val)
  185.    looks for an opponents piece to capture or attack with 1 to 3 liberties.
  186.    for each cell, check to see if its liberties are minlib and if so
  187.      invoke initmark.  evaluate move via findopen.  if findopen returns
  188.      1, then assign value to possible move.
  189.    select new move with highest value and return 1.
  190.    returns 0 if findopen never succeeded.
  191.  
  192.  
  193. initmark()
  194.    initialize ma array to zero.
  195.  
  196.  
  197. findopen(m, n, i, j, color, minlib, ct)
  198.    called by findwinner to find all open spaces for opponent's piece.
  199.    marks m,n entry in ma array.
  200.    for each neighbor, if neighbor is empty spot and not last place captured,
  201.      then count till all spaces are found and return 1 and move in i and j.
  202.      else if spot is color and not marked, then recurse returning 1 if
  203.              any subinvocation returns 1.
  204.  
  205.  
  206. findsaver(i, j, val)
  207.    find move if any pieces of 1 to 3 liberties is threatened
  208.    count how many pieces have minlib liberties.
  209.    if none, return 0.
  210.    else, for each cell, if one of computer's pieces and liberty is minlib,
  211.              then initmark(), and look for move via findnextmove.  if succeeds
  212.              then assign value for possible move.  decrement count of pieces
  213.                   threatened and select next move with maximum value and return
  214.                   1.
  215.   If no new move can be found then return zero and exit.
  216.  
  217. findpatn(i, j)
  218.        if previous invocation of findpatn marked, then invoke opening
  219.            in that corner.  if opening can find a move on a vacant square, 
  220.            then mark this invocation and return value.  if not, then
  221.            clear mark and investigate corners.
  222.        for each marked corner (all corners initially marked), look to see if
  223.            opening can find a move by calling opening() twice.  if it can, 
  224.            mark invocation and return that move.
  225.        for each side, look to see if a particular large empty region exists,
  226.            if it does, make a particular move into that region.
  227.        use mathpat on each board location looking for pattern-moves to make
  228.        and select move with maximum value.
  229.        if none of these find something, return 0.
  230.  
  231.  
  232. matchpat(m, n, i, j, val)
  233.       for each given pattern, try all ways of placing them down with a corner
  234.       at m,n.  return recommended i,j and value if match found.  pattern
  235.       notation specifies cells that should be empty, where pieces of both sides
  236.       should be, whether must be on edge, and recommended move.  patterns
  237.       consist of at most 16 specified locations.  Try all patterns for each
  238.       piece and select the one with highest value.  Adjust value for patterns
  239.       to expand territories in favor of move at third and fourth line. Reduce
  240.       value for move at first and second line. Return 1 if pattern found else
  241.       return zero.
  242.  
  243.  
  244. openregion(i1, j1, i2, j2)
  245.        checks to see if rectangular region is all empty.
  246.  
  247.  
  248. opening(i, j, cnd, type)
  249.      type keeps track of which corner, move is reflected thru corner and
  250.        chosen without actually looking at board.
  251.      cnd indicates which move to make this time.  a move consists of a
  252.        location relative to a corner and a count of how many useful
  253.        different followup moves there all.  the useful followups are listed
  254.        by index into the same structure -- the one recommended for next
  255.        move is chosen randomly among possible moves.
  256.      first time in, location -1,-1 is returned. this value is always ignored.
  257.  
  258.  
  259. sethand(i)
  260.    setup handicap stones by brute force analysis.
  261.  
  262.  
  263. endgame()
  264.    keeps count of captures removed by user cleaning up board, keeps track
  265.    of dame placed by user cleaning up board, and uses findcolor to classify
  266.    territories.  final count presented with updated board showing how 
  267.    everything was classified.
  268.  
  269.  
  270. findcolor(i, j)
  271.       determines what color to label empty squares when counting up score
  272.       at end of game.  algorithm is to check both north and south neighbors
  273.       until run into occupied square or end of board.  if both are vacant
  274.       then east and west neighbors checked same way.  if both are vacant
  275.       return zero.  if one neighbor zero and other nonzero, return color
  276.       of nonzero neighbor.  if both neighbors nonzero and same, then return
  277.       that color. if both neighbors nonzero but differ, then return zero.
  278.  
  279.  
  280. showinst()
  281.      shows program header and a list of instructions to user.
  282.  
  283.  
  284. fioe(i, j)
  285.      check if new move (i, j) will fill in own eye at center and edge.  Only
  286.      single hole eye is checked.
  287.  
  288.  
  289. fval(newlib, minlib)
  290.      used in findnextmove in findnext.c.  Calculate relative value for new
  291.      move having newlib liberties with old pieces having minlib liberties.  
  292.